/**
 * 
 */
package dataStructures;

/**
 * @author filiperosa
 *
 */
public class OrderedDoublyLL<K extends Comparable<K>, V> implements OrderedDictionary<K, V> {

    // Node at the head of the list.
    protected DListNode<Entry<K,V>> head;

    // Node at the tail of the list.
    protected DListNode<Entry<K,V>> tail;
    
    

    // Number of elements in the list.
    protected int currentSize;
    
    public OrderedDoublyLL(){
    	currentSize=0;
    }
	
	@Override
	public boolean isEmpty() {
		 return currentSize==0;
	}

	@Override
	public int size() {
		return currentSize;
	}

	@Override
	public V find(K key) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public V insert(K key, V value) {
		// TODO Auto-generated method stub
		return null;
	}
	
	 // Inserts the specified element at the first position in the list.
    private void addFirst(K key, V value )
    {
        DListNode<Entry<K,V>> newNode = new DListNode(new EntryClass(key, value), null, head);
        if ( this.isEmpty() )
            tail = newNode;
        else
            head.setPrevious(newNode);
        head = newNode;
        currentSize++;
    }


    // Inserts the specified element at the last position in the list.
    private void addLast(K key, V value)
    {
    	DListNode<Entry<K,V>> newNode = new DListNode(new EntryClass(key, value), null, head);
    	if ( this.isEmpty() )
            head = newNode;
        else
            tail.setNext(newNode);
        tail = newNode;
        currentSize++;
    }


    // Inserts the specified element at the specified position in the list.
    // Pre-condition: position ranges from 1 to currentSize-1.
    private void addMiddle(K key, V value, DListNode node)
    {
        DListNode<Entry<K,V>> prevNode = node.getPrevious();
        //DListNode<Entry<K,V>> nextNode = prevNode.getNext();
        DListNode<Entry<K,V>> newNode = new DListNode(new EntryClass(key,value), prevNode, node);
        prevNode.setNext(newNode);            
        node.setPrevious(newNode);            
        currentSize++;
    }

	@Override
	public V remove(K key) {
		// TODO Auto-generated method stub
		return null;
	}
	
	// Removes the first node in the list.
    // Pre-condition: the list is not empty.
    private void removeFirstNode( )
    {
        head = head.getNext();
        if ( head == null )
            tail = null;
        else
            head.setPrevious(null);
        currentSize--;
    }


    // Removes and returns the element at the first position in the list.
    private Entry<K,V> removeFirst( ) throws EmptyListException
    {
        if ( this.isEmpty() )
            throw new EmptyListException();

        Entry<K, V> element = head.getElement();
        this.removeFirstNode();
        return element;
    }


    // Removes the last node in the list.
    // Pre-condition: the list is not empty.
    private void removeLastNode( )
    {
        tail = tail.getPrevious();
        if ( tail == null )
            head = null;
        else
            tail.setNext(null);
        currentSize--;
    }


    // Removes and returns the element at the last position in the list.
    private Entry<K,V> removeLast( ) throws EmptyListException
    {
        if ( this.isEmpty() )
            throw new EmptyListException();

        Entry<K,V> element = tail.getElement();
        this.removeLastNode();
        return element;
    }


    // Removes the specified node from the list.
    // Pre-condition: the node is neither the head nor the tail of the list.
    private void removeMiddleNode( DListNode<Entry<K,V>> node )
    {
        DListNode<Entry<K,V>> prevNode = node.getPrevious();
        DListNode<Entry<K,V>> nextNode = node.getNext();
        prevNode.setNext(nextNode);            
        nextNode.setPrevious(prevNode);            
        currentSize--;
    }


    // Removes and returns the element at the specified position in the list.
    // Range of valid positions: 0, ..., size()-1.
    // If the specified position is 0, remove corresponds to removeFirst. 
    // If the specified position is size()-1, remove corresponds to removeLast.
    private V remove( int position ) throws InvalidPositionException
    {
    	
        if ( position == 0 )
            return this.removeFirst();
        else if ( position == currentSize - 1 )
            return this.removeLast();
        else 
        {
            DListNode<E> nodeToRemove = this.getNode(position);
            this.removeMiddleNode(nodeToRemove);
            return nodeToRemove.getElement();
        }
    }

	@Override
	public Iterator<Entry<K, V>> iterator() {
		return new DoublyLLIterator<EntryClass<K,V>>(head, tail);
	}

	@Override
	public Entry<K, V> minEntry() throws EmptyDictionaryException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Entry<K, V> maxEntry() throws EmptyDictionaryException {
		// TODO Auto-generated method stub
		return null;
	}

}
